/*
 
 
 ********
 WARNING: OUT OF DATE VERSION
 This is a working version of KyleCache.cpp that is limited to simulating a single core processor. This file was renamed to preserve the code (before SVN was set up). Look for the latest KyleCache.cpp for the multi-core verison of this tool
 
 ****************
 
 
 This is a cache simulation tool created by Kyle Roden at the University of Alabama in Huntsville.
 
 The user specifies parameters for various caches and then runs the tool to analyze the execution of any program. After the completion of the program, the statistics on cache accesses can be found in kylecache.out.
 
 The caches are stored as arrays of 64 bit integers, where each row consists of a cache set divided into blocks.  Because this is a simulation, there is no need to store the actual data. Only tags are stored. 
 
 This code is derived from code copyright by Intel and is provided with their open source Pin package.  Very little original Intel is present in this file, but I will include their copyright information anyway.
 
 
 http://www.pintool.org/
 
 Pin is required to use this program. But it's open source! Use the link above to get pin.


**Compile instructions
You need the makefile that should be in the same directory as this source.

use: "make PIN_HOME=<top level directory where pin is installed>"

or simply "make" if pin is at /pin

**Execution
$<path-to-pin>/pin -t <path-to-this-folder>/obj-intel64/KyleCache.so -- <path to target executable> [target exe arguments]

 */ 

/*   
 
 Intel Open Source License 
 
 Copyright (c) 2002-2011 Intel Corporation. All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are
 met:
 
 Redistributions of source code must retain the above copyright notice,
 this list of conditions and the following disclaimer.  Redistributions
 in binary form must reproduce the above copyright notice, this list of
 conditions and the following disclaimer in the documentation and/or
 other materials provided with the distribution.  Neither the name of
 the Intel Corporation nor the names of its contributors may be used to
 endorse or promote products derived from this software without
 specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INTEL OR
 ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 END_LEGAL 
 
 */

#include <stdio.h>
#include <stdlib.h>
#include "pin.H"
#include <iostream>
#include <fstream>
#include <string.h>

static UINT64 icount = 0; //total count of instructions
//static UINT64 ihits = 0; // instruction cache hits
static UINT64 rcount = 0; //count of data reads
static UINT64 wcount = 0; //count of data writes
//static UINT64 l1hits = 0; //total data cache hits


//file to hold results
ofstream results;

//second file for optional debug info.
FILE * trace;



enum ReplacementPolicy{
    RoundRobin = 0,
    LeastRecentlyUsed = 1,
    PseudoRandom = 2
}; //enum for all the currently implemented replacement policies

struct CacheInfo{
  
    UINT32 size;                // total size of cache, in bytes
    UINT32 blockSize;           // size of a cache line/block in bytes
    UINT32 assoc;               // set associativity of cache. 
    UINT32 numRows;             // calculated value for performance. numRows=size/blockSize/assoc 
                                // any object using numRows should calculate it once first.
    ReplacementPolicy policy;   // replacement policy used by this cache
    
    UINT64 hits;
    UINT64 misses;
    string desc;
    
    CacheInfo():
    
    size(0),
    blockSize(0),
    assoc(0),
    numRows(0),
    policy(RoundRobin),
    hits(0),
    misses(0)
    {}

}; //structure to hold information about the cache.

class Cache{
  
public:
    
    //Cache();
    // constructor requires a CacheInfo object. calls initCache
    
    Cache(CacheInfo info){
        
        cacheInfo=info;
        
         initCache();
        
        
    }
    // allocate memory for the cache array
    void initCache(){
        
        cacheInfo.numRows = cacheInfo.size/cacheInfo.blockSize/cacheInfo.assoc;
        
        cache = (UINT64*) malloc(sizeof(UINT64)*cacheInfo.numRows*(cacheInfo.assoc+1));
        
        for(UINT64 i=0; i<cacheInfo.numRows*(cacheInfo.assoc+1);i++)
            cache[i]=0;
        if (cache == NULL){
            cout<< "could not allocate " << sizeof(UINT64)*cacheInfo.numRows*(cacheInfo.assoc+1) <<" bytes of memory for a cache. Exiting.";
            exit(5);
            
        }
    }
    
    // return a copy of the cache info
    CacheInfo getCacheInfo(){
        
        return cacheInfo;
    }
    
    bool searchCache(VOID *ip){
        //TODO: improve efficiency of the following three calculations using bitwise operators and shifting, etc
        
        
        UINT64 cacheTag = UINT64(ip)/(cacheInfo.numRows*cacheInfo.blockSize);
        UINT64 cacheRow = UINT64(ip)%(cacheInfo.numRows*cacheInfo.blockSize)/cacheInfo.blockSize;
        
        UINT64 rowPos = cacheRow * (cacheInfo.assoc + 1); //position of the row
        
        for (unsigned int i=0;i<cacheInfo.assoc;i++)
            if( cache[rowPos+i] == cacheTag ) { 
                cacheInfo.hits++;
                /*if(icount<1000){
                    fprintf(trace,"inst %lu hit in %s.\n",icount, cacheInfo.desc.c_str()); 
                }*///DEBUG
                
                return true;  //item was found in cache, return.
            }
        
        
        /*if(icount<1000){
            fprintf(trace,"inst %lu missed in %s.\n",icount, cacheInfo.desc.c_str());
        }*///DEBUG
        cacheInfo.misses++;
        
        int evictee = chooseEvictee(rowPos); //use replacement policy to choose which item to evict

        
        cache[rowPos+evictee] = cacheTag;    // "evict" specified item and add data to cache
              
        return false; //was not found in cache. was added to cache.
        
                
    }
              
    int chooseEvictee(UINT64 rowPos){
        
        int evictee;
        
        switch(cacheInfo.policy){
                
            case LeastRecentlyUsed:
                // TODO: insert logic here
                break;
                
                
            case RoundRobin: 
                evictee = cache[rowPos+cacheInfo.assoc]; //read round robin counter
                cache[rowPos+cacheInfo.assoc]= //increment round robin counter
                    (cache[rowPos+cacheInfo.assoc] + 1) % cacheInfo.assoc;
                return evictee; 
                break;
                
            case PseudoRandom:
                // TODO: insert logic here
                break;
        
            default: //if no replacment policy specified, or if it was random, we do random
                //TODO: insert logic here
                break;
    
        }
    
    //this should never be reached
        return 0;
    
    }
    
private:
    
    CacheInfo cacheInfo; //holds the structure containing cache specifications
    
    UINT64 *cache;  //pointer to the array representing this cache
    
    
}; //class contains structural details for each cache, the actual cache memory object, and cache functions


//two arrays of pointers to all caches used. 0 is the first level cache, and the rest are in order.
Cache ** insCacheList;
Cache ** dataCacheList;
int insCacheCount, dataCacheCount;


// called for every instruction fetch
VOID everyInstr(VOID *ip)
{ 
    icount++;
    for (int i=0; i<insCacheCount;i++)
      if(insCacheList[i]->searchCache(ip))
          break;
}
   
// called for every memory read operation. 
VOID RecordMemRead(VOID * ip, VOID * addr)
{
    rcount++;
    for (int i=0; i<dataCacheCount;i++)
        if(dataCacheList[i]->searchCache(ip))
          break;
        
}

// called for each memory write operation. 
VOID RecordMemWrite(VOID * ip, VOID * addr)
{
    wcount++;
    for (int i=0; i<dataCacheCount;i++)
        if(dataCacheList[i]->searchCache(ip))
          break;
        
}

// Is called for every instruction and instruments reads and writes
VOID Instruction(INS ins, VOID *v)
{
    // Instruments memory accesses using a predicated call, i.e.
    // the instrumentation is called iff the instruction will actually be executed.
    //
    // The IA-64 architecture has explicitly predicated instructions. 
    // On the IA-32 and Intel(R) 64 architectures conditional moves and REP 
    // prefixed instructions appear as predicated instructions in Pin.
    UINT32 memOperands = INS_MemoryOperandCount(ins);
    
    
    //every instruction
    INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)everyInstr, IARG_INST_PTR, IARG_END);
    
    // Iterate over each memory operand of the instruction.
    for (UINT32 memOp = 0; memOp < memOperands; memOp++)
    {
        if (INS_MemoryOperandIsRead(ins, memOp))
        {
            INS_InsertPredicatedCall(
                                     ins, IPOINT_BEFORE, (AFUNPTR)RecordMemRead,
                                     IARG_INST_PTR,
                                     IARG_MEMORYOP_EA, memOp,
                                     IARG_END);
        }
        // Note that in some architectures a single memory operand can be 
        // both read and written (for instance incl (%eax) on IA-32)
        // In that case we instrument it once for read and once for write.
        if (INS_MemoryOperandIsWritten(ins, memOp))
        {
            INS_InsertPredicatedCall(
                                     ins, IPOINT_BEFORE, (AFUNPTR)RecordMemWrite,
                                     IARG_INST_PTR,
                                     IARG_MEMORYOP_EA, memOp,
                                     IARG_END);
        }	
    }
}

//This function is run at program termination
VOID Fini(INT32 code, VOID *v){
    
//DEBUG: prints a final cache dump 
/*   
     results << "\n L1 cache dump:\n";
     for (unsigned int i=0;i<l1DataCacheRows;i++){
        for (unsigned int j=0;j<(l1DataCacheAssoc+1);j++)
            results << hex<<l1DataCache[i][j] <<", ";
        results<<endl;
     }*/    
    
    
    results << "Results:\n\n"<<dec;
    results << "Total instructions: "<<icount;
    results << "\nMemory read requests: "<<rcount;
    results << "\nMemory write requests: "<<wcount<<endl<<endl;
    
    for(int i=0; i<insCacheCount ; i++){
        results <<"Instruction Cache #"<<i<<endl;
        results <<"Hits: "<<insCacheList[i]->getCacheInfo().hits<<endl;
        results <<"Misses: "<<insCacheList[i]->getCacheInfo().misses<<endl;
        results << "\nInstruction cache misses per 1000: ";
        results <<(
                   1-float(insCacheList[i]->getCacheInfo().hits)/
                   float(insCacheList[i]->getCacheInfo().hits+
                         insCacheList[i]->getCacheInfo().misses+1)
                   )*1000<<endl<<endl;
        
    }
    for(int i=0; i<dataCacheCount ; i++){
        results <<"Data Cache #"<<i<<endl;
        results <<"Hits: "<<dataCacheList[i]->getCacheInfo().hits<<endl;
        results <<"Misses: "<<dataCacheList[i]->getCacheInfo().misses<<endl;
        results << "Data cache misses per 1000: ";
        results <<(
                   1-float(dataCacheList[i]->getCacheInfo().hits)/
                   float(dataCacheList[i]->getCacheInfo().hits+
                         dataCacheList[i]->getCacheInfo().misses+1)
                   )*1000<<endl<<endl;
        
    }
    fprintf(trace, "#eof\n");
    fclose(trace);
    
    results.close();
}

//print usage instructions
INT32 Usage()
{
    PIN_ERROR( "This Pintool simulates a user defined cache and prints metrics to a file\n" 
              + KNOB_BASE::StringKnobSummary() + "\n");
    return -1;
}

//main
int main(int argc, char *argv[])
{
    
    if (PIN_Init(argc, argv)) return Usage();
    
    results.open("kylecache.out");
    trace = fopen("kylecache2.out", "w");
    
    
    //temporary until we are reading this stuff from a file
    insCacheCount = 1;
    dataCacheCount = 2;
    CacheInfo datainfo[dataCacheCount];
    CacheInfo insinfo[insCacheCount];
    CacheInfo instrinfo; instrinfo.size=8192 , instrinfo.blockSize=32, instrinfo.assoc=4, instrinfo.policy=RoundRobin, instrinfo.desc="l1ins";
    CacheInfo data1info; data1info.size=8192 , data1info.blockSize=32, data1info.assoc=4, data1info.policy=RoundRobin, data1info.desc="l1data";
    CacheInfo data2info; data2info.size=262114, data2info.blockSize=32, data2info.assoc=4, data1info.policy=RoundRobin, data2info.desc="l2data";
    
    datainfo[0]=data1info;
    datainfo[1]=data2info;
    insinfo[0]=instrinfo;
    
    dataCacheList = new Cache*[dataCacheCount];
    
    //one iteration for every level of data cache. create each cache
    for (int i=0; i<dataCacheCount; i++)
        dataCacheList[i] = new Cache(datainfo[i]);
    
    if(insCacheCount){ //check to see if we have any seperate instruction caches.
        insCacheList = new Cache*[insCacheCount];
        for(int i=0;i<insCacheCount;i++)
            insCacheList[i] = new Cache(insinfo[i]);
    }
    else 
    {
        insCacheList = dataCacheList;  //no dedicated instruction cache(s)
        insCacheCount = dataCacheCount;  
    }
    
    
    INS_AddInstrumentFunction(Instruction, 0);
    PIN_AddFiniFunction(Fini, 0);
    


    // Never returns
    PIN_StartProgram();
    
    return 0;
    }
